



import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

def edit_distance_visual(str1, str2):
    m = len(str1)
    n = len(str2)

    # 创建一个(m+1) x (n+1) 的矩阵
    dp = [[0 for x in range(n + 1)] for x in range(m + 1)]

    # 填充矩阵
    for i in range(m + 1):
        for j in range(n + 1):
            # 如果 str1 为空，插入所有 str2 的字符
            if i == 0:
                dp[i][j] = j    # Min. operations = j

            # 如果 str2 为空，删除所有 str1 的字符
            elif j == 0:
                dp[i][j] = i    # Min. operations = i

            # 如果最后一个字符相同，忽略最后一个字符并递归其余字符串
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]

            # 如果最后一个字符不同，考虑所有可能的操作并选择最小值
            else:
                dp[i][j] = 1 + min(dp[i][j-1],    # 插入
                                   dp[i-1][j],    # 删除
                                   dp[i-1][j-1])  # 替换

    # 创建用于展示的 DataFrame
    df = pd.DataFrame(dp, index=[''] + list(str1), columns=[''] + list(str2))
    return df

# 测试代码
str1 = "kitten"
str2 = "sitting"
df = edit_distance_visual(str1, str2)

# 使用 seaborn 和 matplotlib 可视化 DataFrame
plt.figure(figsize=(10, 8))
sns.heatmap(df, annot=True, fmt="d", cmap="YlGnBu", cbar=False, linewidths=.5)
plt.title(f"Edit Distance between '{str1}' and '{str2}'")
plt.xlabel('String 2')
plt.ylabel('String 1')
plt.show()

print(f"The edit distance between '{str1}' and '{str2}' is {df.iloc[-1, -1]}")


